package leetcode.Hot100;

import leetcode.ListNode;

import java.util.ArrayList;
import java.util.Comparator;

/**
 * @author Cheng Jun
 * Description: 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
 * 进阶：
 * 你可以在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
 * <p>
 * 链接：https://leetcode-cn.com/problems/sort-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/12/8 14:32
 * <p>
 * 输入：head = [4,2,1,3]
 * 输出：[1,2,3,4]
 * 链表中节点的数目在范围 [0, 5 * 104] 内
 * -10^5 <= Node.val <= 10^5
 */
public class sortList {

    // 简单粗暴
    ListNode sortList(ListNode head) {
        ListNode dummy = new ListNode(0);
        ListNode p = dummy;
        ArrayList<ListNode> arr = new ArrayList<>();
        while (head != null) {
            arr.add(head);
            head = head.next;
        }
        arr.sort(Comparator.comparingInt(l -> l.val));
        for (ListNode listNode : arr) {
            p.next = listNode;
            p = p.next;
            listNode.next = null;
        }
        return dummy.next;
    }

    // 常数级空间复杂度 创建的ListNode 数量固定
    ListNode sortList1(ListNode head) {
        return null;
    }
}
